package 热题100.动态规划.完全平方数_279_中等;
/*
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9

提示：
1 <= n <= 104

思路：
    看这时间复杂度就是n2了。
    含义：f[j]表示和为j的完全平方数的最少数量，注意这是数量
    状态转移方程； f[j] = min(f[j], f[j - i * i] + 1)，即当前这个i我选不选，这个和完全背包是一样的
    初始化： f[j] = 0，f[1] = 1， 其他的f[i]都是最大值
* */
public class Solution {
    public static void main(String[] args) {
        System.out.println(numSquares(5));
    }

    public static int numSquares(int n) {
        int[] f = new int[n + 1];
        for (int i = 0; i <= n; i ++){
            f[i] = Integer.MAX_VALUE - 1; // 防止更新的时候超过范围
        }
        f[0] = 0;
        // 先遍历i，i^2 > n再遍历i就没意义了，等同于先遍历物品，这里从1开始是因为w[0] = 0 * 0没有重量w，而背包的w[0]有价值，
        // 用0来更新的话， f[1 - 0 *0 ] + 1 就会超过范围，但是把max减少1就行了
        for (int i = 0; i * i <= n ; i ++){
            // 再遍历背包， 背包最少都要装i*i
            for (int j = i * i; j <= n; j ++){
                f[j] = Math.min(f[j], f[j - i * i] + 1);
            }
        }
        return f[n];
    }
}
